package momo.multitree.structure;

import java.io.FileReader;
import java.io.StringReader;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Vector;

import momo.multitree.visual.GraphVizGraphOutput;
import momo.multitree.visual.PajekGraphOutput;

import junit.framework.TestCase;


public class GraphTest extends TestCase {

	private Graph graph;
	
	protected void setUp() throws Exception {
		super.setUp();
		graph = new Graph();
	}

	protected void tearDown() throws Exception {
		super.tearDown();
		graph = null;
	}
	
	public void testAdd()
	{
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Edge edge = new Edge("1", node1, node2, 1, 1, 1, 1);
		assertEquals(true, graph.add(edge) );
	}
	
	public void testGetEdge() {
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Node node3 = new Node("3", 1, 1);
		Node node4 = new Node("4", 1, 1);
		Edge edge1 = new Edge("1", node1, node2, 1, 1, 1, 1);
		Edge edge2 = new Edge("2", node1, node3, 1, 1, 1, 1);
		Edge edge3 = new Edge("3", node1, node4, 1, 1, 1 ,1);
		graph.add(edge1);
		graph.add(edge2);
		graph.add(edge3);
		
		assertEquals(edge1, graph.getEdge(node1, node2));
		assertEquals(edge1, graph.getEdge(node2, node1));
		assertEquals(edge2, graph.getEdge(node1, node3));
		assertEquals(edge2, graph.getEdge(node3, node1));
		assertEquals(edge3, graph.getEdge(node1, node4));
		assertEquals(edge3, graph.getEdge(node1, node4));
		
		
	}
	
	public void testAddDuplicateEdge()
	{
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Edge edge = new Edge("1", node1, node2, 1, 1, 1, 1);
		graph.add(edge);
		assertEquals(false, graph.add(edge) );
	}
	
	public void testAddDuplicateNode()
	{
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Node node3 = new Node("3", 1, 1);
		Edge edge1 = new Edge("1", node1, node2, 1, 1, 1, 1);
		Edge edge2 = new Edge("2", node1, node3, 1, 1, 1, 1);
		graph.add(edge1);
		graph.add(edge2);
		Set<Node> set = graph.getNodes();
		assertEquals(3, set.size());
	}
	
	public void testGetEdgesOfNode()
	{
		Vector<Edge> vec = new Vector<Edge>();
		
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Node node3 = new Node("3", 1, 1);
		Node node4 = new Node("4", 1, 1);
		Edge edge1 = new Edge("1", node1, node2, 1, 1, 1, 1);
		Edge edge2 = new Edge("2", node1, node3, 1, 1, 1, 1);
		Edge edge3 = new Edge("3", node1, node4, 1, 1, 1 ,1);
		vec.add(edge1);
		vec.add(edge2);
		vec.add(edge3);
		graph.add(edge1);
		graph.add(edge2);
		graph.add(edge3);
		Set<Edge> set = graph.getEdgesOfNode(node1);
		Iterator<Edge> iter = set.iterator();
		while ( iter.hasNext() )
		{
			assertTrue(vec.remove(iter.next()));
		}
		assertEquals(0, vec.size());
	}
	
	public void testCompare()
	{
		Node root = new Node("1", 0.5, 0.6); //root node
		Node node2 = new Node("2", 0.1, 0.3);
		Node node3 = new Node("3", 0.1, 0.8);
		Node node4 = new Node("4", 0.1, 0.4);
		Node node5 = new Node("5", 0.2, 0.9);
		
		Edge edge1 = new Edge("1", root, node2, 5, 2, 6, 6);
		Edge edge2 = new Edge("2", root, node3, 4, 3, 3, 3);
		Edge edge3 = new Edge("3", node2, node4, 1, 7, 2, 2);
		Edge edge4 = new Edge("4", node2, node5, 10, 0, 1, 1);
		
		Graph graphA = new Graph();
		graphA.add(edge1);
		graphA.add(edge2);
		graphA.add(edge3);
		graphA.add(edge4);
		
		Node root11 = new Node("1", 0.5, 0.6); //root node
		Node node21 = new Node("2", 0.1, 0.3);
		Node node31 = new Node("3", 0.1, 0.8);
		Node node41 = new Node("4", 0.1, 0.4);
		Node node51 = new Node("5", 0.2, 0.9);
		
		Edge edge11 = new Edge("11", root11, node21, 5, 2, 6, 6);
		Edge edge21 = new Edge("21", root11, node31, 4, 3, 3, 3);
		Edge edge31 = new Edge("31", node21, node41, 1, 7, 2, 2);
		Edge edge41 = new Edge("41", node21, node51, 10, 0, 1, 1);
		
		Graph graphB = new Graph();
		graphB.add(edge11);
		graphB.add(edge21);
		graphB.add(edge31);
		graphB.add(edge41);
		
		assertTrue(graphB.compare(graphA));
	}
	
	public void testIsConnected()
	{
		Node root = new Node("1", 0.5, 0.6); //root node
		Node node2 = new Node("2", 0.1, 0.3);
		Node node3 = new Node("3", 0.1, 0.8);
		Node node4 = new Node("4", 0.1, 0.4);
		Node node5 = new Node("5", 0.2, 0.9);
		
		Edge edge1 = new Edge("1", root, node2, 5, 2, 6, 6);
		Edge edge2 = new Edge("2", root, node3, 4, 3, 3, 3);
		Edge edge3 = new Edge("3", node2, node4, 1, 7, 2, 2);
		Edge edge4 = new Edge("4", node2, node5, 10, 0, 1, 1);
		
		Graph graphA = new Graph();
		graphA.add(edge1);
		graphA.add(edge2);
		graphA.add(edge3);
		graphA.add(edge4);
		
		assertTrue(graphA.isConnectedGraph());
		
		Node node6 = new Node("6", 1, 1);
		Node node7 = new Node("7", 1, 1);
		Edge edge5 = new Edge("5", node6, node7, 1, 1, 1, 1);
		graphA.add(edge5);
		
		assertTrue(!graphA.isConnectedGraph());
	}
	
	public void testRemoveEdge()
	{
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Node node3 = new Node("3", 1, 1);
		Node node4 = new Node("4", 1, 1);
		Node node5 = new Node("5", 1, 1);
		Node node6 = new Node("6", 1, 1);
		
		Edge edge1 = new Edge("1", node1, node3, 1, 1, 1, 1);
		Edge edge2 = new Edge("2", node2, node3, 1, 1, 1, 1);
		Edge edge3 = new Edge("3", node3, node4, 1, 1, 1, 1);
		Edge edge4 = new Edge("4", node5, node4, 1, 1, 1, 1);
		Edge edge5 = new Edge("5", node6, node4, 1, 1, 1, 1);
		
		Graph graphA = new Graph();
		graph.add(edge1);
		graph.add(edge2);
		graph.add(edge3);
		graph.add(edge4);
		graph.add(edge5);
		
		//remove the bridge
		graph.remove(edge3);
		
		//check edges set
		Vector<Edge> vecLeftEdges = new Vector<Edge>();
		vecLeftEdges.add(edge1);
		vecLeftEdges.add(edge2);
		vecLeftEdges.add(edge4);
		vecLeftEdges.add(edge5);
		
		Set<Edge> edgesLeft = graph.getEdges();
		Iterator<Edge> iterEdgesLeft = edgesLeft.iterator();
		while( iterEdgesLeft.hasNext() )
			assertTrue(vecLeftEdges.remove(iterEdgesLeft.next()));
		assertEquals(0, vecLeftEdges.size());
		
		//check out edges set
		Vector<Edge> outEdgeOfNode1 = new Vector<Edge>();
		outEdgeOfNode1.add(edge1);
		Set<Edge> set1 = graph.getEdgesOfNode(node1);
		Iterator<Edge> iter1 = set1.iterator();
		while ( iter1.hasNext() )
			assertTrue(outEdgeOfNode1.remove(iter1.next()));
		assertEquals(0, outEdgeOfNode1.size());
		
		Vector<Edge> outEdgeOfNode2 = new Vector<Edge>();
		outEdgeOfNode2.add(edge2);
		Set<Edge> set2 = graph.getEdgesOfNode(node2);
		Iterator<Edge> iter2 = set2.iterator();
		while ( iter2.hasNext() )
			assertTrue(outEdgeOfNode2.remove(iter2.next()));
		assertEquals(0, outEdgeOfNode2.size());
		
		Vector<Edge> outEdgeOfNode3 = new Vector<Edge>();
		outEdgeOfNode3.add(edge1);
		outEdgeOfNode3.add(edge2);
		Set<Edge> set3 = graph.getEdgesOfNode(node3);
		Iterator<Edge> iter3 = set3.iterator();
		while ( iter3.hasNext() )
			assertTrue(outEdgeOfNode3.remove(iter3.next()));
		assertEquals(0, outEdgeOfNode3.size());
		
		Vector<Edge> outEdgeOfNode4 = new Vector<Edge>();
		outEdgeOfNode4.add(edge4);
		outEdgeOfNode4.add(edge5);
		Set<Edge> set4 = graph.getEdgesOfNode(node4);
		Iterator<Edge> iter4 = set4.iterator();
		while ( iter4.hasNext() )
			assertTrue(outEdgeOfNode4.remove(iter4.next()));
		assertEquals(0, outEdgeOfNode4.size());
		
		Vector<Edge> outEdgeOfNode5 = new Vector<Edge>();
		outEdgeOfNode5.add(edge4);
		Set<Edge> set5 = graph.getEdgesOfNode(node5);
		Iterator<Edge> iter5 = set5.iterator();
		while ( iter5.hasNext() )
			assertTrue(outEdgeOfNode5.remove(iter5.next()));
		assertEquals(0, outEdgeOfNode5.size());
		
		Vector<Edge> outEdgeOfNode6 = new Vector<Edge>();
		outEdgeOfNode6.add(edge5);
		Set<Edge> set6 = graph.getEdgesOfNode(node6);
		Iterator<Edge> iter6 = set6.iterator();
		while ( iter6.hasNext() )
			assertTrue(outEdgeOfNode6.remove(iter6.next()));
		assertEquals(0, outEdgeOfNode6.size());
	}
	
	public void testHasCycle()
	{
		Graph graphA = new Graph();
		Node root = new Node("1", 1, 1);
		Node nodeA = new Node("6", 1, 1);
		Node nodeB = new Node("7", 1, 1);
		
		Edge edgeA = new Edge("1", root, nodeA, 1, 1, 1, 1);
		Edge edgeB = new Edge("2", nodeA, nodeB, 1, 1, 1, 1);
		Edge edgeC = new Edge("3", nodeB, root, 1, 1, 1, 1);
		
		graphA.add(edgeA);
		graphA.add(edgeB);
		graphA.add(edgeC);
		
		assertTrue(graphA.hasCycle());
	}
	
	public void testOutputVisual()
	{
		try
		{
			String filename = "5_node_symmetric_dataset_1.txt";
			Graph g = new Graph(new FileReader("dataset/"+filename));
			
			g.outputVisual("5_node_symmetric_dataset_1");
		}catch(Exception e)
		{
			e.printStackTrace();
		}
	}
	
	public void testOutputDatasetFile()
	{
		try
		{
			String filename = "5_node_symmetric_dataset_1.txt";
			String newFilename = "5_node_symmetric_dataset_1_test.txt";
			Graph g1 = new Graph(new FileReader("dataset/"+filename));
			
			g1.outputDatasetFile("dataset/"+newFilename);
			Graph g2 = new Graph(new FileReader("dataset/"+newFilename));
			assertTrue(g1.compare(g2));
		}catch (Exception e)
		{
			e.printStackTrace();
		}
	}
	
	public void testLeftConnectedGraph()
	{
		Node n1 = new Node("1", 1, 1);
		Node n2 = new Node("2", 1, 1);
		Node n3 = new Node("3", 1, 1);
		Node n4 = new Node("4", 1, 1);
		Edge e1 = new Edge("1", n1, n2, 1, 1, 1, 1);
		Edge e2 = new Edge("2", n1, n3, 1, 1, 1, 1);
		Edge e3 = new Edge("3", n4, n3, 1, 1, 1, 1);
		
		Node n5 = new Node("5", 1, 1);
		Node n6 = new Node("6", 1, 1);
		Node n7 = new Node("7", 1, 1);
		Edge e4 = new Edge("4", n5, n6, 1, 1, 1, 1);
		Edge e5 = new Edge("5", n5, n7, 1, 1, 1, 1);
		
		Node n8 = new Node("8", 1, 1);
		
		graph.add(e1);
		graph.add(e2);
		graph.add(e3);
		graph.add(e4);
		graph.add(e5);
		graph.add(n8);
		
		Graph g1 = graph.clone();
		Graph g2 = graph.clone();
		Graph g3 = graph.clone();
		
		g1.leftConnectedGraph(n3);
		g2.leftConnectedGraph(n6);
		g3.leftConnectedGraph(n8);
		
		assertTrue( g1.contains(n1) );
		assertTrue( g1.contains(n2) );
		assertTrue( g1.contains(n3) );
		assertTrue( g1.contains(n4) );
		assertTrue( !g1.contains(n5) );
		assertTrue( !g1.contains(n6) );
		assertTrue( !g1.contains(n7) );
		assertTrue( !g1.contains(n8) );
		assertTrue( g1.contains(e1) );
		assertTrue( g1.contains(e2) );
		assertTrue( g1.contains(e3) );
		assertTrue( !g1.contains(e4) );
		assertTrue( !g1.contains(e5) );
		
		assertTrue( !g2.contains(n1) );
		assertTrue( !g2.contains(n2) );
		assertTrue( !g2.contains(n3) );
		assertTrue( !g2.contains(n4) );
		assertTrue( g2.contains(n5) );
		assertTrue( g2.contains(n6) );
		assertTrue( g2.contains(n7) );
		assertTrue( !g2.contains(n8) );
		assertTrue( !g2.contains(e1) );
		assertTrue( !g2.contains(e2) );
		assertTrue( !g2.contains(e3) );
		assertTrue( g2.contains(e4) );
		assertTrue( g2.contains(e5) );
		
		assertTrue( !g3.contains(n1) );
		assertTrue( !g3.contains(n2) );
		assertTrue( !g3.contains(n3) );
		assertTrue( !g3.contains(n4) );
		assertTrue( !g3.contains(n5) );
		assertTrue( !g3.contains(n6) );
		assertTrue( !g3.contains(n7) );
		assertTrue( g3.contains(n8) );
		assertTrue( !g3.contains(e1) );
		assertTrue( !g3.contains(e2) );
		assertTrue( !g3.contains(e3) );
		assertTrue( !g3.contains(e4) );
		assertTrue( !g3.contains(e5) );
		
	}
	
	public void testGetLeafEdges() {
		Node n1 = new Node("1", 1, 1);
		Node n2 = new Node("2", 1, 1);
		Node n3 = new Node("3", 1, 1);
		Node n4 = new Node("4", 1, 1);
		Edge e1 = new Edge("1", n1, n2, 1, 1, 1, 1);
		Edge e2 = new Edge("2", n1, n3, 1, 1, 1, 1);
		Edge e3 = new Edge("3", n4, n3, 1, 1, 1, 1);
		
		graph.add(e1);
		graph.add(e2);
		graph.add(e3);
		
		Set<Edge> leafEdges = graph.getLeafEdges();
		assertTrue( leafEdges.contains(e1) );
		assertFalse( leafEdges.contains(e2) );
		assertTrue( leafEdges.contains(e3) );
	}
	
	public void testGetNonLeafEdges() {
		Node n1 = new Node("1", 1, 1);
		Node n2 = new Node("2", 1, 1);
		Node n3 = new Node("3", 1, 1);
		Node n4 = new Node("4", 1, 1);
		Edge e1 = new Edge("1", n1, n2, 1, 1, 1, 1);
		Edge e2 = new Edge("2", n1, n3, 1, 1, 1, 1);
		Edge e3 = new Edge("3", n4, n3, 1, 1, 1, 1);
		
		graph.add(e1);
		graph.add(e2);
		graph.add(e3);
		
		Set<Edge> nonLeafEdges = graph.getNonLeafEdges();
		assertFalse( nonLeafEdges.contains(e1) );
		assertTrue( nonLeafEdges.contains(e2) );
		assertFalse( nonLeafEdges.contains(e3) );
	}
	
}//end of class GraphTest
